//实现一个 MapSum 类，支持两个方法，insert 和 sum： 
//
// 
// MapSum() 初始化 MapSum 对象 
// void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 
//key 已经存在，那么原来的键值对将被替代成新的键值对。 
// int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//inputs = ["MapSum", "insert", "sum", "insert", "sum"]
//inputs = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
//输出：
//[null, null, 3, null, 5]
//
//解释：
//MapSum mapSum = new MapSum();
//mapSum.insert("apple", 3);  
//mapSum.sum("ap");           // return 3 (apple = 3)
//mapSum.insert("app", 2);    
//mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)
// 
//
// 
//
// 提示： 
//
// 
// 1 <= key.length, prefix.length <= 50 
// key 和 prefix 仅由小写英文字母组成 
// 1 <= val <= 1000 
// 最多调用 50 次 insert 和 sum 
// 
//
// 
//
// 
// 注意：本题与主站 677 题相同： https://leetcode-cn.com/problems/map-sum-pairs/ 
//
// Related Topics 设计 字典树 哈希表 字符串 👍 22 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class MapSum {

    class Trie{
        Trie[] children;
        boolean isEnd;
        Integer value;

        public Trie(){
            children = new Trie[26];
            isEnd = false;
        }
    }

    Trie root;

    /** Initialize your data structure here. */
    public MapSum() {
        root = new Trie();
    }
    
    public void insert(String key, int val) {
        Trie node = root;
        for(int i = 0; i < key.length(); i++){
            char c = key.charAt(i);
            int index = c - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
        node.value = val;
    }

    int sum = 0;  //sum单独拿到外面为啥不行？
    private int searchPrefix(String prefix){
        Trie node = root;
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            int index = c - 'a';
            if(node.children[index] == null){
                return 0;
            }
            node = node.children[index];
        }
//        return traversal(node, 0); // 到此处方可确定str为一合法前缀，通过dfs返回其子树空间中的值（以其为前缀的key的值）
        travsersal2(node);
        return sum;
    }

    //sum单独拿到外面为啥不行？
    private int traversal(Trie node, int sum){
        if(node.isEnd) sum += node.value;
        Trie[] arr = node.children;
        for(int i = 0; i < arr.length; i++){
            Trie temp = arr[i];
            if(temp == null){
                continue;
            }
            sum += traversal(temp, 0); //注意是dfs(child, 0)而不是dfs(child, sum)
        }
        return sum;
    }

    //sum单独拿到外面为啥不行?因为sum是全局变量，之前调用sum的时候sum已经变成3了，再次调用sum游加了5
    private void travsersal2(Trie node){
        for(Trie item : node.children){
            if(item == null){
                continue;
            }
            if(item.isEnd){
                sum += item.value;
            }
            travsersal2(item);
        }
    }
    
    public int sum(String prefix) {
        return searchPrefix(prefix);
    }

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        mapSum.insert("app", 2);
        int ap = mapSum.sum("ap");
        System.out.println(ap);
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */
//leetcode submit region end(Prohibit modification and deletion)
